{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Alternating Subsequence Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxAlternatingSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大子序列交替和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个下标从 <strong>0</strong> 开始的数组的 <strong>交替和</strong> 定义为 <strong>偶数</strong> 下标处元素之 <strong>和</strong> 减去 <strong>奇数</strong> 下标处元素之 <strong>和</strong> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，数组 <code>[4,2,5,3]</code> 的交替和为 <code>(4 + 5) - (2 + 3) = 4</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个数组 <code>nums</code> ，请你返回 <code>nums</code> 中任意子序列的 <strong>最大交替和</strong> （子序列的下标 <strong>重新</strong> 从 0 开始编号）。</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p>一个数组的 <strong>子序列</strong> 是从原数组中删除一些元素后（也可能一个也不删除）剩余元素不改变顺序组成的数组。比方说，<code>[2,7,4]</code> 是 <code>[4,<strong>2</strong>,3,<strong>7</strong>,2,1,<strong>4</strong>]</code> 的一个子序列（加粗元素），但是 <code>[2,4,2]</code> 不是。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><b>示例 1：</b></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [<strong>4</strong>,<strong>2</strong>,<strong>5</strong>,3]\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>最优子序列为 [4,2,5] ，交替和为 (4 + 5) - 2 = 7 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [5,6,7,<strong>8</strong>]\n",
    "<b>输出：</b>8\n",
    "<b>解释：</b>最优子序列为 [8] ，交替和为 8 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [<strong>6</strong>,2,<strong>1</strong>,2,4,<strong>5</strong>]\n",
    "<b>输出：</b>10\n",
    "<b>解释：</b>最优子序列为 [6,1,5] ，交替和为 (6 + 5) - 1 = 10 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-alternating-subsequence-sum](https://leetcode.cn/problems/maximum-alternating-subsequence-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-alternating-subsequence-sum](https://leetcode.cn/problems/maximum-alternating-subsequence-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,5,3]', '[5,6,7,8]', '[6,2,1,2,4,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums) -> int:\n",
    "        tmp_res = -99999999\n",
    "        sub_list = []\n",
    "        # dp[i][0]:从0到i之间子序列为奇数的最大和\n",
    "        # dp[i][1]:从0到i之间子序列为偶数的最大和\n",
    "        dp = [[tmp_res]*2 for _ in range(len(nums))]\n",
    "        dp[0] = [nums[0], 0]\n",
    "        for i in range(1, len(nums)):\n",
    "            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + nums[i])\n",
    "            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - nums[i])\n",
    "        return max(dp[len(nums)-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0, -inf] for _ in range(n + 1)]\n",
    "        for i, x in enumerate(nums):\n",
    "            dp[i + 1][1] = max(dp[i][1], dp[i][0] + x)\n",
    "            dp[i + 1][0] = max(dp[i][0], dp[i][1] - x)\n",
    "        return dp[n][1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i < 0:\n",
    "        #         return 0 if j == 0 else -inf\n",
    "        #     if j == 1:\n",
    "        #         return max(dfs(i - 1, 1), dfs(i - 1, 0) + nums[i])\n",
    "        #     return max(dfs(i - 1, 0), dfs(i - 1, 1) - nums[i])\n",
    "        # return dfs(n - 1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        dp = [[0 for _ in range(4)] for _ in range(len(nums)+1)]\n",
    "        # 1: add 2: minus 3: sameAdd 4: sameMiuns\n",
    "        dp[0][0] = nums[0]\n",
    "        dp[0][1] = 0\n",
    "        dp[0][2] = nums[0]\n",
    "        dp[0][3] = 0\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "                dp[i][0] = max(nums[i], dp[i][0], dp[i-1][1]+nums[i], dp[i-1][3]+nums[i])\n",
    "                if dp[i-1][0] != 0:\n",
    "                    dp[i][1] = max(dp[i][1], dp[i-1][0]-nums[i])\n",
    "                if dp[i-1][2] != 0:\n",
    "                    dp[i][1] = max(dp[i][1], dp[i-1][2]-nums[i])\n",
    "                dp[i][2] = max(dp[i][2], dp[i-1][0], dp[i-1][2])\n",
    "                dp[i][3] = max(dp[i][3], dp[i-1][1], dp[i-1][3])\n",
    "        res = 0\n",
    "        \n",
    "\n",
    "        for i in range(len(dp)):\n",
    "            for j in range(4):\n",
    "                res = max(res, dp[i][j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        dp = np.zeros((len(nums), 2), np.uint64)\n",
    "        dp[0][0] = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            dp[i][0] = max(dp[i-1][1] + nums[i], dp[i-1][0])\n",
    "            dp[i][1] = max(dp[i-1][0] - nums[i], dp[i-1][1])\n",
    "        return dp[-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [ [[0] * 2 for _ in range(2)] for _ in range(n + 1)]\n",
    "        ret = 0\n",
    "        for i in range(1, n + 1):\n",
    "            f[i][0][0] = max(f[i - 1][0][0], f[i - 1][1][0])\n",
    "            f[i][1][0] = max(f[i - 1][0][1], f[i - 1][1][1]) + nums[i - 1]\n",
    "            f[i][0][1] = max(f[i - 1][0][1], f[i - 1][1][1])\n",
    "            f[i][1][1] = max(f[i - 1][0][0], f[i - 1][1][0]) - nums[i - 1]\n",
    "            ret = max(ret, f[i][0][0], f[i][1][0], f[i][0][1], f[i][1][1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        dp = {}\n",
    "        dp[(0,True)] = nums[0]\n",
    "        dp[(0,False)] = 0\n",
    "        res = nums[0]\n",
    "        pre_max_t = nums[0]\n",
    "        pre_max_f = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            max_t, max_f = nums[i], None\n",
    "            #print(max_t, max_f)\n",
    "            #for j in range(i):\n",
    "            j = i-1\n",
    "            if dp[(j,False)] + nums[i] > max_t:\n",
    "                max_t = dp[(j,False)] + nums[i]\n",
    "            if not max_f or dp[(j,True)] - nums[i] > max_f:\n",
    "                max_f = dp[(j,True)] - nums[i]\n",
    "            dp[(i,True)] = max(max_t, pre_max_t)\n",
    "            dp[(i,False)] = max(max_f, pre_max_f)\n",
    "            pre_max_t = max(pre_max_t, dp[(i,True)])\n",
    "            pre_max_f = max(pre_max_f, dp[(i,False)])\n",
    "            res = max(max_t,max_f,pre_max_t,pre_max_f)\n",
    "        #print(dp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        @functools.lru_cache(maxsize=None)\n",
    "        def dp(i: int, odd: bool):\n",
    "            if i == len(nums):\n",
    "                return 0\n",
    "            if odd:\n",
    "                return max(dp(i + 1, True), dp(i + 1, False) - nums[i])\n",
    "            else:\n",
    "                return max(dp(i + 1, False), dp(i + 1, True) + nums[i])\n",
    "        \n",
    "        for i in range(len(nums), 0, -1):\n",
    "            dp(i, True)\n",
    "            dp(i, False)\n",
    "            \n",
    "        answer = dp(0, False)\n",
    "        dp.cache_clear()\n",
    "        return answer \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        gmin, gmax = self.subProblem(nums, 0)\n",
    "        return gmax\n",
    "    \n",
    "    def subProblem(self, nums, i):\n",
    "        # returns (min, max)\n",
    "        if i == len(nums) - 1:\n",
    "            return min(nums[-1], 0), max(0, nums[-1])\n",
    "        \n",
    "        # consider subproblem\n",
    "        submin, submax = self.subProblem(nums, i + 1)\n",
    "\n",
    "        maxm = max(nums[i] - submin, submax)\n",
    "        minm = min(nums[i] - submax, submin)\n",
    "\n",
    "        return minm, maxm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        opt_odd = 0\n",
    "        self.nums = nums\n",
    "        opt_even = nums[0]\n",
    "        self.init_v = nums[0]\n",
    "        self.opt_evens = {}\n",
    "        self.opt_odds = {}\n",
    "        return self.myEven(n - 1)\n",
    "    def myEven(self, i):\n",
    "        if i == 0:\n",
    "            return self.init_v\n",
    "        if (i in self.opt_evens.keys()):\n",
    "            return self.opt_evens[i]\n",
    "        opt_even = max(self.myOdd(i - 1) + self.nums[i], self.myEven(i - 1))\n",
    "        self.opt_evens[i] = opt_even\n",
    "        return opt_even\n",
    "    def myOdd(self, i):\n",
    "        if i == 0:\n",
    "            return 0\n",
    "        if (i in self.opt_odds.keys()):\n",
    "            # print('ues')\n",
    "            return self.opt_odds[i]\n",
    "        opt_odd = max(self.myEven(i - 1) - self.nums[i], self.myOdd(i - 1))\n",
    "        self.opt_odds[i] = opt_odd\n",
    "        return opt_odd\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        res = float('-inf')\n",
    "        table = {}\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            res = max(res, self.search(nums, i, 1, table))\n",
    "        return res\n",
    "        \n",
    "    def search(self, nums, i, status, table):\n",
    "        if (i, status) not in table:\n",
    "            n = len(nums)\n",
    "            if i == n:\n",
    "                table[(i, status)] = 0\n",
    "            else:\n",
    "                table[(i, status)] = max(self.search(nums, i + 1, status, table), status * nums[i], status * nums[i] + self.search(nums, i + 1, -1 * status, table))\n",
    "        return table[(i, status)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        self.nums = nums\n",
    "        self.memo = {}\n",
    "        self.res = nums[0]\n",
    "        res_1 = self.dp(len(nums) - 1, 0)\n",
    "        res_2 = self.dp(len(nums) - 1, 1)\n",
    "        # print(self.memo)\n",
    "        return self.res\n",
    "    # 选择 第i个元素是否是作为子序列中的奇数/偶数\n",
    "    # 状态 第i个元素 子序列中的奇数/偶数\n",
    "    # 定义 dp(i, j)\n",
    "    def dp(self, i, j):\n",
    "        # 如果是第一个数字，那么只能是选择作为第一个数字，或者不选择\n",
    "        if i == 0:\n",
    "            if j == 0:\n",
    "                return self.nums[0]\n",
    "            else:\n",
    "                return 0\n",
    "        if (i, j) in self.memo.keys():\n",
    "            return self.memo[i, j]\n",
    "        # \n",
    "        # 如果j是偶数\n",
    "        if j == 0:\n",
    "            # \n",
    "            res = max(self.dp(i - 1, 0), self.dp(i - 1, 1) + self.nums[i])\n",
    "\n",
    "        elif j == 1:\n",
    "            res = max(self.dp(i - 1, 1), self.dp(i - 1, 0) - self.nums[i])\n",
    "\n",
    "        self.memo[i, j] = res\n",
    "        self.res = max(self.res, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        def masInner(nums: List[int], modd: Dict[int, int], mevn: Dict[int, int], index: int, odd: bool) -> int:\n",
    "            if index >= len(nums):\n",
    "                return 0\n",
    "            elif odd: # try find min value\n",
    "                if index in modd:\n",
    "                    return modd[index]\n",
    "                else:\n",
    "                    # pick current vs. not picking\n",
    "                    m = max(-nums[index] + masInner(nums, modd, mevn, index + 1, False), masInner(nums, modd, mevn, index + 1, True))\n",
    "                    modd[index] = m\n",
    "                    return m\n",
    "            else: # !odd\n",
    "                if index in mevn:\n",
    "                    return mevn[index]\n",
    "                else:\n",
    "                    m = max(nums[index] + masInner(nums, modd, mevn, index + 1, True), masInner(nums, modd,mevn, index + 1, False))\n",
    "                    mevn[index] = m\n",
    "                    return m\n",
    "\n",
    "        return masInner(nums, {}, {}, 0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def helper(left:int, right:int)->int:\n",
    "            if left>right: return 0\n",
    "            if left == right: \n",
    "                if right!=n-1:\n",
    "                    return 0\n",
    "                else: return nums[left]\n",
    "\n",
    "\n",
    "            point_one = left\n",
    "            \n",
    "            while point_one+1<=right and nums[point_one+1]>nums[point_one]:\n",
    "                point_one+=1\n",
    "            \n",
    "            point_two = point_one\n",
    "\n",
    "            while point_two+1<=right and nums[point_two+1]<=nums[point_two]:\n",
    "                point_two+=1\n",
    "\n",
    "            # print(left, right, point_one, point_two)\n",
    "            if point_two!=n-1:\n",
    "                return nums[point_one]-nums[point_two] + helper(point_two+1, right)\n",
    "            else: return nums[point_one]\n",
    "        \n",
    "        return helper(0, len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def crossSum(i):\n",
    "            if not i:\n",
    "                return [0, nums[0]] # [odd, even]\n",
    "            odd, even = crossSum(i-1)\n",
    "            return [max(odd, even-nums[i]), max(even, odd+nums[i])]\n",
    "        \n",
    "        return max(crossSum(len(nums)-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        @lru_cache\n",
    "        def dfs(idx, flag):\n",
    "            if idx==len(nums):\n",
    "                return 0\n",
    "            T1 = dfs(idx+1, flag)\n",
    "            if flag:\n",
    "                T2 = nums[idx] + dfs(idx+1, 1-flag)\n",
    "            else:\n",
    "                T2 = -nums[idx] + dfs(idx+1, 1-flag)\n",
    "            return max(T1, T2)\n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = nums[-1]\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return 0, 0\n",
    "            mx, mi = dfs(i + 1)\n",
    "            opt1 = nums[i] - mx\n",
    "            opt2 = nums[i] - mi\n",
    "            opt3 = mx\n",
    "            opt4 = mi\n",
    "            tmp = (opt1, opt2, opt3, opt4)\n",
    "            nonlocal ans\n",
    "            ans = max(ans, max(tmp))\n",
    "            return max(tmp), min(tmp)\n",
    "        dfs(0)[0]\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        positive = [-1] * len(nums)\n",
    "        negative = [1] * len(nums)\n",
    "        nega_b = [False] * len(nums)\n",
    "\n",
    "        def posi(i):\n",
    "            if i >= len(nums):\n",
    "                return 0\n",
    "            if positive[i] != -1:\n",
    "                return positive[i]\n",
    "            positive[i] = max(nums[i] + nega(i + 1), posi(i + 1))\n",
    "            return positive[i]\n",
    "\n",
    "        def nega(i):\n",
    "            if i >= len(nums):\n",
    "                return 0\n",
    "            if nega_b[i]:\n",
    "                return negative[i]\n",
    "            negative[i] = max(posi(i + 1) - nums[i], nega(i + 1))\n",
    "            nega_b[i] = True\n",
    "            return negative[i]\n",
    "\n",
    "        return posi(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, flag):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            \n",
    "            res = dfs(idx + 1, flag)\n",
    "            if flag:\n",
    "                res = max(res, nums[idx] + dfs(idx + 1, 0))\n",
    "            else:\n",
    "                res = max(res, -nums[idx] + dfs(idx + 1, 1))\n",
    "            return res\n",
    "        \n",
    "        ans = dfs(0, 1)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        m=len(nums)\n",
    "        @lru_cache(None)\n",
    "        def dfs(deep,ids):\n",
    "            if ids == m:\n",
    "                return 0\n",
    "            if deep == 0:\n",
    "                ans=nums[ids]\n",
    "                return max(ans+dfs((deep+1)%2,ids+1),dfs(deep,ids+1))\n",
    "            else:\n",
    "                ans=nums[ids]*(-1)\n",
    "                return max(ans+dfs((deep+1)%2,ids+1),dfs(deep,ids+1))\n",
    "        ret=dfs(0,0)\n",
    "        dfs.cache_clear()\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        info_dict={}\n",
    "        def recur_solution(tail):\n",
    "            if tail in info_dict:\n",
    "                return info_dict[tail]\n",
    "            if tail==0:\n",
    "                info_dict[tail]=nums[0],0\n",
    "                return nums[0],0\n",
    "            else:\n",
    "                even,odd=recur_solution(tail-1)\n",
    "                temp_even=max(even,odd+nums[tail])\n",
    "                temp_odd=max(odd,even-nums[tail])\n",
    "                info_dict[tail]=temp_even,temp_odd\n",
    "                return temp_even,temp_odd\n",
    "        \n",
    "        result1,result2=recur_solution(len(nums)-1)\n",
    "        return max(result1,result2)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        cache = [{}, {}]\n",
    "        \n",
    "        # e[i] = max(nums[i] + o[i + 1], e[i + 1])\n",
    "        # o[i] = max(-nums[i] + e[i + 1], o[i + 1])\n",
    "        def dfs(i, oe):\n",
    "            if i == len(nums):\n",
    "                return 0\n",
    "            if i in cache[oe]:\n",
    "                return cache[oe][i]\n",
    "            res = 0\n",
    "            if oe == 0:\n",
    "                res = max(nums[i] + dfs(i + 1, 1), dfs(i + 1, 0))\n",
    "            else:\n",
    "                res = max(-nums[i] + dfs(i + 1, 0), dfs(i + 1, 1))\n",
    "            cache[oe][i] = res\n",
    "            return res\n",
    "\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def helper(i, odd):\n",
    "            if i<0:\n",
    "                return 0 if not odd else -inf\n",
    "            else:\n",
    "                if odd:\n",
    "                    return max(helper(i-1, True), helper(i-1, False)+nums[i])\n",
    "                else:\n",
    "                    return max(helper(i-1, False), helper(i-1, True)-nums[i])\n",
    "        return max(max(helper(i, False), helper(i, True)) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def helper(idx):\n",
    "            if idx == n - 1:\n",
    "                return 0, nums[-1]\n",
    "            \n",
    "            left, right = helper(idx + 1)\n",
    "            minus = min(nums[idx] - right, left)\n",
    "            add = max(nums[idx] - left, right)\n",
    "            return minus, add\n",
    "        \n",
    "        return helper(0)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def helper(i, odd): # 前i中子序列 最后一个元素奇偶状态是odd 交替和最大值 \n",
    "            if i<0:\n",
    "                return 0 if not odd else -inf # 如果第一个值不是偶那就返回-inf，表示不可能取\n",
    "            else:\n",
    "                if odd:\n",
    "                    return max(helper(i-1, True), helper(i-1, False)+nums[i])\n",
    "                else:\n",
    "                    return max(helper(i-1, False), helper(i-1, True)-nums[i])\n",
    "        return max(helper(i, True) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def f(n):\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            return max(f(n - 1),g(n - 1) + nums[n - 1])\n",
    "        @cache\n",
    "        def g(n):\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            return max(g(n - 1),f(n - 1) - nums[n - 1])\n",
    "        return f(len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def getOdd(i):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            else:\n",
    "                return max(nums[i] + getEven(i+1), getOdd(i+1))\n",
    "            \n",
    "        @cache\n",
    "        def getEven(i):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            else:\n",
    "                return max(-nums[i] + getOdd(i+1), getEven(i+1))\n",
    "            \n",
    "        n = len(nums)\n",
    "        return getOdd(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i, ma=True):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            if ma:\n",
    "                # use i\n",
    "                ans = nums[i] - dfs(i + 1, False)\n",
    "                # ignore i \n",
    "                ans = max(ans, dfs(i + 1))\n",
    "            else:\n",
    "                ans = nums[i] - dfs(i + 1)\n",
    "                ans = min(ans, dfs(i + 1, False))\n",
    "            return ans\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        dp = {}\n",
    "        def dfs(i, even):\n",
    "            if i == len(nums):\n",
    "                return 0\n",
    "            if (i, even) in dp:\n",
    "                return dp[(i, even)]\n",
    "            total = nums[i] if even else -1 * nums[i]\n",
    "            dp[(i, even)] = max(total + dfs(i + 1, not even), dfs(i + 1, even))\n",
    "            return dp[(i, even)]\n",
    "        return dfs(0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        dp = {}\n",
    "        def dfs(i, even):\n",
    "            if i == len(nums):\n",
    "                return 0\n",
    "            if (i, even) in dp:\n",
    "                return dp[(i, even)]\n",
    "            total = nums[i] if even else -nums[i]\n",
    "            dp[(i, even)] = max(dfs(i + 1, not even) + total, dfs(i + 1, even))\n",
    "            return dp[(i, even)]\n",
    "        return dfs(0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        dp = {}\n",
    "        # even is true if starts with adding the first value\n",
    "        def dfs(i, even):\n",
    "            if i == len(nums):\n",
    "                return 0\n",
    "            if (i, even) in dp:\n",
    "                return dp[(i, even)]\n",
    "            total = -nums[i] if even is False else nums[i]\n",
    "            dp[(i, even)] = max(total + dfs(i + 1, not even),\n",
    "                                dfs(i + 1, even))\n",
    "            return dp[(i, even)]\n",
    "        return dfs(0, True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        def dfs(p, f):\n",
    "            if p == len(nums):\n",
    "                return 0\n",
    "            if (p, f) in dp:\n",
    "                return dp[(p, f)]\n",
    "            ret = dfs(p+1, f)\n",
    "            if f == 0:\n",
    "                ret = max(ret, nums[p] + dfs(p + 1, 1 - f))\n",
    "            else:\n",
    "                ret = max(ret, -nums[p] + dfs(p + 1, 1 - f))\n",
    "            dp[(p, f)] = ret\n",
    "            return ret\n",
    "            \n",
    "        dp = {}\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        # uses a tuple (i, even) as the key\n",
    "        dp = {}\n",
    "        \n",
    "        # i = index, even = True/False\n",
    "        def action(i, even):\n",
    "            if i == len(nums):\n",
    "                return 0\n",
    "            if (i, even) in dp:\n",
    "                return dp[(i,even)]\n",
    "            \n",
    "            total = nums[i] if even else (-1 * nums[i])\n",
    "            dp[(i, even)] = max(total + action(i+1, not even), action(i+1, even))\n",
    "            return dp[(i,even)]\n",
    "        return action(0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums):\n",
    "        memo = {}\n",
    "\n",
    "        def dp(idx, l):\n",
    "            key = (idx, l % 2)\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "            if idx == len(nums):\n",
    "                return 0\n",
    "            if l % 2 == 0:\n",
    "                ret = max(dp(idx + 1, l + 1) + nums[idx], dp(idx + 1, l))\n",
    "            elif l % 2 == 1:\n",
    "                ret = max(dp(idx + 1, l + 1) - nums[idx], dp(idx + 1, l))\n",
    "            memo[key] = ret\n",
    "            return ret\n",
    "\n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "import sys\n",
    "sys.setrecursionlimit(999999)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def dp1(ii):\n",
    "            if ii == 0:\n",
    "                return nums[ii]\n",
    "\n",
    "            return max(nums[ii] + dp2(ii-1), dp1(ii-1))\n",
    "\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def dp2(ii):\n",
    "            if ii == 0:\n",
    "                return 0\n",
    "\n",
    "            return max((-nums[ii]) + dp1(ii-1), dp2(ii-1))\n",
    "\n",
    "\n",
    "        return dp1(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAlternatingSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i >= n: return 0\n",
    "            ans = dfs(i + 1, j)\n",
    "            if j:\n",
    "                ans = max(ans, dfs(i + 1, 0) - nums[i])\n",
    "            else:\n",
    "                ans = max(ans, dfs(i + 1, 1) + nums[i])\n",
    "            return ans\n",
    "        return dfs(0, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
